Template matching is a processing for detecting an image region having highest correlation to a template image region from on a reference image. The template matching is used in processings for searching a similar image, tracking an object, detecting motion vector in motion picture coding, and the like.
Non-patent document 1 describes conventional template matching technologies in detail in a chapter 6.
1. A method of defining a degree of similarity showing the difference between a partial region (reference image region) on a reference image nominated as a matching candidate and a template image and finding a reference image region for minimizing the degree of similarity is ordinarily used as a template matching method. Used as the degree of similarity is, for example, the average value of the signal value differences of the respective pixels between a reference image region and a template image (MAD: Mean Absolute Difference), the average value of the squares of signal value differences (MSE: Mean Square Error), and the like.
As a basic method of the template matching, a method of calculating degrees of similarity to all the candidates and detecting a reference image region for minimizing them is called an all search method. Although the all search method can detect the reference image region that minimizes the degree of similarity without error, it is very ineffective from a view point of an amount of calculation.
A method called a multistep search method or a rough/fine search method is widely used as a conventional technology for reducing the amount of calculation of the template matching. This is a method of dividing a template matching processing to plural steps. According to the method, at a first step, image regions are widely and roughly searched by evaluating the positions of reference image regions nominated as similar region candidates after the positions of them are thinned out at rough intervals, and, in the matching at second and subsequent steps, the similar region candidates are narrowed down stepwise by narrowly and finely searching only the peripheries of the image regions selected in the previous step.
FIG. 2 is a schematic view showing an example of the multistep search method. A lattice pattern in the figure shows the coordinates of a reference image region nominated as a matching candidate. In the example, a template matching processing is executed at two steps. At a first step, the degrees of similarity of the reference image regions labeled by 1 in FIG. 2 are calculated, and the image region that minimizes an evaluated value is selected as a similar image region. In FIG. 2, when it is assumed that the reference image region surrounded by a circle and shown by 1 is selected, at a next second step, the degrees of similarity of the reference image regions labeled by 2 in FIG. 2 are calculated, and the reference image region that minimizes a degree of similarity in the reference image regions surrounded by a circle and labeled by 1 and 2 is selected as a similar image region.
In the example, since 15×15=225 pieces of reference image regions are listed as matching candidates, when a matching processing is executed by the all search method, it requires to calculate the degree of similarity 225 times. The number of times of calculation can be reduced to 7×7=49 times at first step and to 8 times at a second step, that is, to 57 times in total by using the multistep search method.
Note that there is practically used a method of using a reference image reduced to low resolution at a previous step and a template image to further reduce the amount of calculation of the multistep search method. For example, at a first step of the example of FIG. 1, when the degree of similarity is calculated using an image having resolution reduced to ½ both horizontally and vertically, since the amount of calculation for calculating the degree of similarity once is reduced to about ¼, the amount of calculation can be more reduced than a simple multistep search method.
However, the multistep search method assumes such a property that the degree of similarity smoothly changes with respect to the positions of the reference image regions as a precondition for accurately executing matching. Accordingly, when an image having many fine pictures and edges and an image including many noises are input, the precondition is not established, and thus an image region whose degree of similarity is not small may be detected in the matching at a first step.
FIG. 3 shows an example of erroneous detection. A graph shows the degree of similarity that can be obtained from a template image and a reference image. Two minimal points exist in the example, and the right minimal point of them corresponds to the most similar reference image region as a correct answer. It is assumed that the left minimal point is a local minimum point less similar than the right one. When the multistep search method is applied to the example and the calculation of the degree of similarity at a first matching step is limited only to the positions shown by the large black circles in a broken line, the left minimal point, which is only a local minimum point, is erroneously detected.
The erroneous detection is liable to occur when two or more minimal points of the degree of similarity exist, and the calculation of the degree of similarity that takes a minimum point is thinned out. In particular, when a degree of similarity containing the sum of the differences of respective pixels is used as in MAD, since the degree of similarity is increased even if it is slightly dislocated from a minimal point, an erroneous detection ratio is increased.
An essential countermeasure for preventing the erroneous detection is to reduce the intervals of reference image regions whose degree of similarity is calculated at a first step or to select plural matching image regions at a first step and to execute matching in the peripheries of the plural image regions at a second step. However, since the number of times of calculation of the degree of similarity is increased, this countermeasure is not practical from the view point of the amount of calculation.
As a method of improving the accuracy of matching at a first step without increasing the number of times of calculation of the degree of similarity, there is contemplated a method of interpolatingly estimating the degrees of similarity of the positions located among the positions, which are located at rough intervals and the degrees of similarity of which are calculated, from the calculated degrees of similarity. For example, the parametric template method of the non-patent document 2 improves detection accuracy at a first step by interpolating a correlation coefficient by expressing it by a quadratic continuous function. However, the method has a restriction in that the degree of similarity is limited to the correlation coefficient. Further, a problem may arise in a load of a matrix calculation necessary to the interpolation.
It is also contemplated to make use of degree of similarity interpolation methods called equiangular fitting and parabola fitting, which are known as a degree of similarity interpolation method at a first step of the multistep search method. In the equiangular interpolation and the parabola interpolation, the degree of similarity calculated among three points is continuously interpolated by applying a broken line or a parabola that is symmetrical about a minimal point to the calculated degree of similarity (FIG. 14). These methods are used in a problem called subpixel estimation for estimating a position with accuracy higher than the resolution of an input image, and the subpixel estimation is used to improve the accuracy of a position of a similar image after the position is found once with integer pixel accuracy (non-patent document 3). However, in a status in which erroneous detection occurs in a multistep search, the intervals at which a degree of similarity is calculated are insufficient as compared with the fineness of a template image, many noises are included, or the degree of similarity is not symmetrical at a minimal point in many cases.
Accordingly, there is required a degree of similarity estimation method in which a local minimal solution does not fall even in the above cases.
Non-patent Document 1: A Murat Tekalp, “Digital Video Processing” Prentice Hall PTR, 1995
Non-patent document 2: K. Tanaka, M. Sano, S. Ohara, M. Okudara, “A parametic template method and its application to robust matching,” in Proc. of IEEE Conference on Computer Vision and Pattern Recognition, 2000.
Non-patent document 3: Masao Shimizu and Masatoshi Okutomi, “Significance and Attributes of Sub-Pixel Estimation on Area-Based Matching”, Systems and Computers in Japan, Vol. 34, No. 12, pp. 1-10, November 2003.